package com.adee.nowcoder.huawei;

import java.util.*;

public class T050_HJ050 {
    // https://blog.csdn.net/CHR_1s/article/details/81564558
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String s = in.nextLine();
            String ops = "()+-*/%";
            s = s.replaceAll(" ", "")
                    .replaceAll("\\{", "(")
                    .replaceAll("\\[", "(")
                    .replaceAll("\\}", ")")
                    .replaceAll("\\]", ")");
            // 中缀表达式转后缀表达式
            // https://blog.csdn.net/qq_40705355/article/details/106646978
            // 一、中缀表达式转换为后缀表达式
            //你需要设定一个栈SOP,和一个线性表 L 。SOP用于临时存储运算符和左括号分界符( ，L用于存储后缀表达式。
            //遍历原始表达式中的每一个表达式元素
            //（1）如果是操作数，则直接追加到 L中。只有 运算符 或者 分界符（ 才可以存放到 栈SOP中
            //（2）如果是分界符
            //         Ⅰ 如果是左括号 ( ， 则 直接压入SOP，等待下一个最近的 右括号 与之配对。
            //         Ⅱ 如果是右括号），则说明有一对括号已经配对(在表达式输入无误的情况下)。不将它压栈，丢弃它，然后从SOP中出栈，得到元素e，将e依次追加到L里。一直循环，直到出栈元素e 是 左括号 ( ，同样丢弃他。
            //（3）如果是运算符（用op1表示）
            //        Ⅰ如果SOP栈顶元素（用op2表示） 不是运算符，则二者没有可比性，则直接将此运算符op1压栈。 例如栈顶是左括号 ( ，或者栈为空。
            //        Ⅱ 如果SOP栈顶元素（用op2表示） 是运算符 ，则比较op1和 op2的优先级。如果op1 > op2 ，则直接将此运算符op1压栈。
            //如果不满足op1 > op2，则将op2出栈，并追加到L，重复步骤3。
            //也就是说，如果在SOP栈中，有2个相邻的元素都是运算符，则他们必须满足：下层运算符的优先级一定小于上层元素的优先级，才能相邻。
            //
            //最后，如果SOP中还有元素，则依次弹出追加到L后，就得到了后缀表达式。


            List<String> postList = new ArrayList<>();
            Stack<Node> stack = new Stack<>();
            for(int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                if(ops.charAt(c) >= 0) { // 运算符
                    Node newNode = new Node(c);
                    if(stack.isEmpty()) {
                        stack.push(newNode);
                    } else {
                        Node peekNode = stack.peek();
                        if(Node.ynPush(newNode, peekNode)) {
                            stack.push(newNode);
                        } else {
                            Node pop = stack.pop();
                            postList.add(String.valueOf(pop.op));
                            stack.push(newNode);
                        }
                    }
                } else { // 数字

                }
            }

            // 二、逆波兰表达式计算
            //后缀表达式求值原理:
            //从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素 和 栈顶元素），并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果。
            //
            //例如: (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 - , 针对后缀表达式求值步骤如下:
            //
            //从左至右扫描，将3和4压入堆栈；
            //遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7入栈；
            //将5入栈；
            //接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈；
            //将6入栈；
            //最后是-运算符，计算出35-6的值，即29，由此得出最终结果


        }
    }

    public static class Node {
        int priority; // 优先级
        //boolean isOp; // 是否为运算符，true符号，false数字
        //int num;
        char op; // + - * / % ( )
        // 运算符优先级排序
        // )       1
        // + -     2
        // * / %   3
        // (       4

        public Node(char op) {
            this.op = op;
            if(')' == op) {
                priority = 1;
            } else if('+' == op || '-' == op) {
                priority = 2;
            } else if('*' == op || '/' == op || '%' == op) {
                priority = 3;
            } else if('(' == op) {
                priority = 4;
            }
        }

        // 当前符号优先级大于栈顶符号优先级时，不弹出直接压入；小于等于时，弹出再压入
        public static boolean ynPush(Node newNode, Node peekNode) {
            if(newNode.op == peekNode.op) {
                return true;
            } else {
                if(newNode.op > peekNode.op) {
                    return true;
                } else {
                    // 虽然+比栈顶元素”（ “低但是”（ “只有遇到“ ）”才会出栈，所以需要把+压栈
                    if(newNode.op == ')' && peekNode.op == '(') {
                        return true;
                    } else {
                        return false;
                    }
                }
            }
        }
    }



    public static void main1(String[] args) {
        Stack<Integer> s = new Stack<>();
        s.push(1);
        s.push(2);
        System.out.println(s.peek());
        System.out.println(s.size());
        System.out.println(String.valueOf('('));

        ArrayList<Integer> list = new ArrayList<>();
        list.add(1);
        LinkedList<Integer> list2 = new LinkedList<>();
        list2.add(2);
    }
}
